This invention deals with the interleaving of data streams of differing priorities in such a manner that real time data can be delivered on a managed packet-based network in real time, while non-real time data is delivered in the bandwidth remaining after the real time data has been transmitted.
Historically, entire separate communications systems have been employed to transmit audio data, traditionally referred to as xe2x80x9cvoicexe2x80x9d, and computer data, conveniently referred to as xe2x80x9cdataxe2x80x9d, although at present audio data and computer data both are considered to fall within the broad definition of xe2x80x9cdataxe2x80x9d. Over a century ago analogue telephone networks were developed to carry analogue audio signals. Telephone networks allow communication of audio signals between two or more users by establishing, with central switching equipment, a temporary dedicated communication circuit or channel between the users. Because the channel, once established, is dedicated exclusively to the transmission of signals between the users, the signals are not required to compete for the channel""s bandwidth with other unrelated signals. The advantage of having a dedicated channel for a voice conversation is that any transmission delay from speaker to listener is purely a function of the unfettered speed of the audio signal through the telephone network. Since this speed does not significantly vary over time, such dedicated channels are capable of providing isochronous transmission. Unfortunately, one significant disadvantage of dedicated channels is that they require significant bandwidth; that is, the complete bandwidth of the channel remains available and dedicated to carrying the conversation even when no information is being transmitted, such as during either conversational or inter-syllable pauses. To allow better utilisation of a given communication link, time-division multiplexing (TDM) systems, where voice signals from a number of users are digitised and then the resulting bits are time compressed for transmission over the same link. This scheme also provides isochronous transmission while sharing the communication link.
In contrast, more recent packet transmission systems are asynchronous, allowing the allocation of bandwidth on an as-demanded basis. For instance, if a channel is highly active, it may receive more than its pro-rata share of overall bandwidth. When a channel""s activities decline, its allocated bandwidth likewise declines. Thus, packet transmission is adept at handling xe2x80x9cburstyxe2x80x9d transmission of data, wherein the activity of each individual channel is subject to relatively wide variation.
All networks experience certain delays in end-to-end data transmission therethrough, this delay (termed xe2x80x9clatencyxe2x80x9d) affects the overall efficiency and effective bandwidth of the network. Packet-based computer networks, because they are asynchronous, are further subjected to xe2x80x9cjitterxe2x80x9d, defined as a change in the latency of the network as a function of time. Jitter is largely unpredictable; however, the overall quantity of traffic on a network tends to increase both latency and jitter. Jitter can only be corrected by ensuring constant latency, or by developing methods to compensate for its effects. The most common of these methods is the use of a xe2x80x9cjitter-bufferxe2x80x9d to store incoming data, thus hiding jittery transmissions from the listener.
Given the ongoing rapid growth of data traffic compared with the slow growth of voice traffic, it is foreseeable that the volume of data traffic will outstrip that of voice on public carrier networks. At that point, the existing Public Switched Telephone Network (PSTN), whose technology is primarily based on circuit switching, will be used predominantly to carry data for which a packet switching technology is a more appropriate alternative. Packet-switched networks can carry voice calls using as little as 8 kilobits per second (Kbps) of bandwidth to provide TDM quality voice compared to the 64 Kbps that is reserved for each call in the conventional PSTN. The potential increase in capacity is attractive to telecommunications service providers, as are the reduced infrastructure costs associated with building packet-switched networks. As a result, providers of new real time telephony services are increasingly using packet- switched network architectures, a trend that will continue with the arrival of competition in the local phone market. The predominant packet-based network protocol in use today is the ubiquitous Internet Protocol (IP). The first attempts to use this technology were implemented by hobbyists on the Internet. In these early methods, an Internet telephony software program would convert the user""s analogue voice signal to digital data, compress it, and transmit it as packets to an Internet server. For example, a full duplex real time telephone conversation may be initiated over the Internet from one computer to another. Both computers generally require the same Internet telephony software, a microphone, a sound card, a minimum processor speed, a modem, specific software, and a connection to an Internet Service Provider. Both computers must be on-line simultaneously; which requires either a pre-arrangement between callers or a separate telephone toll call. Software for that type of system is commercially available.
Data packets traverse packet based networks by being routed from one node to the next. Each of these hops takes the packet closer to its destination. Each node along the route is designated by a globally unique address. Each node in the route looks at the destination address contained in the header of a packet and sends the packet in the direction of its destination. At any time, a node along a particular route can stop accepting, or block one or more packets. This may be due to any number of reasons: congestion, maintenance, node crashes, etc. Each routing node constantly monitors its adjacent nodes and adjusts its routing table when problems occur. As a result, sequential packets often take different routes as they traverse the Internet. The audio quality of duplex phone conversation over the Internet is often poor because of delays of transmission of packets, lost packets, and lost connections. The delays are unpredictable and are usually caused by the dynamically changing conditions of the network and the changing and often long routes through which packets must pass to arrive at their destination. One consequence of these delays and differing routes the packets follow, other than message lag, is that individual voice packets may arrive in a non-sequential order.
Existing methods for reducing delay-related problems include assorted error correction schemes, primarily repeat codes, which transmit data packets multiple times, and parity codes, which use modulo arithmetic to achieve a fixed value over a series of cells in a check accumulator. These techniques are well known in the art, as are their drawbacks. The use of repeat codes is undesirable because of the network resources wasted by sending multiple copies of a single packet. Parity codes are hampered by implementation problems that make both source encoding and destination decoding complicated. A simple xe2x80x9crow-parityxe2x80x9d scheme can be employed easily by placing parity packets after a set number of packets, but is flawed because it can only be used to correct an error if the receiver knows that all but one packet has been received correctly. More complex schemes, such as the one outlined in U.S. Pat. No. 5,883,891 use a xe2x80x9cmatrix-parityxe2x80x9d concept which seeks to improve the audio quality of voice communication over the Internet by reconstituting delayed and/or missing packets based upon the packets that arrive in time. The system is xe2x80x9crobustxe2x80x9d, in comparison to simpler row-parity schemes, because packets constituting the matrix are deliberately transmitted over multiple routes. If one route is subject to delays, or packet loss, the lost or delayed packets can be fully reconstituted in many cases. The system receiving the voiceband signal from a caller (host system) uses a software program, which arranges each set of incoming voice packets into a two or three dimensional matrix. For example, a matrix could consist of five rows and five columns for a total of twenty-five packets. A sixth row, composed of check packets and based upon the five packets in its column is added as is a sixth column whose elements are check packets based upon the rows of the matrix. The source node transmits the packets over an IP network, such as the Internet, to a destination node which performs the necessary parity check operations to determine the values of missing and/or delayed packets. If the decoding system is sufficiently fast, the effect, to the listener, is as if all the packets had arrived on time. The listener hears a replica of the entire original voice.
Though parity schemes such as these are more effective than repeat codes, they introduce additional complexity in both the encoding and decoding processes, and still cannot guarantee a quality of service equivalent to that of TDM telephony due to the inherently unpredictable nature of overly used, highly congested, public data networks such as the Internet.
Packet-switching techniques typically involve variable and arbitrary delays, which are unacceptable for two-way communication involving real time signals. The human ear is critically sensitive to absolute delay greater than about 200 ms. The ear is also critically sensitive to random delays or gap modulation, as well as to minute tones, inflections and pauses, particularly in human speech. Thus, a computer data network that must also transmit audio data is forced to cope with the communication of both bursty computer and time-sensitive audio data on the same backbone.
These problems are compounded by call set-up difficulties that arise from an inability to pick an ideal transmission block size. This size is dependent upon numerous factors which include channel capacity, congestion, and data sources. Any packet that is larger than a maximum transmission unit (MTU) must be segmented, which introduces excessive overhead if the MTU is smaller than the majority of data packets from the source. If the MTU is too large on a congested channel, then excessive delays are introduced when non-real-time data is being transmitted and a real-time data packet is waiting for transmission. Thus the establishment of an MTU suitable for network transmission is important to systems that simultaneously contain real-time and non-real-time data packets.
One method of determining the optimal MTU that is known in the art is to determine the maximum packet size that the path in the network between the two nodes can reliably transmit by interrogating the nodes that are passed in transit as to their capacity, and picking a packet size that is as large as the smallest capacity of any node in the route taken through the network. This method is overly restrictive as a result of the fact that the MTU is unable to change in response to dynamic bandwidth fluctuations. In addition to this drawback, the interrogation of a system with high latency can adversely impact upon the time needed to establish a connection (i.e. an increase in the time required for handshaking).
Because the MTU is the largest size a packet can be in a given network, it is common in the art to use the MTU as the segment size for the transport layer for transferring large files. This practice results in a large overhead cost at the host system where the large file is stored. Not only does each segment require substantial overhead when transmitted but each acknowledgement of the transmitted segments effectively doubles the overhead since the overhead per segment is constant regardless of the size of the data transfer.
There has been a universal reluctance to increase the segment size above the network MTU and divide the segments into two or more fragments. This reluctance stems from the fact that transmission protocols such as TCP/IP retransmit the entire segment if any fragment is lost or encounters an error, thus rendering the apparent savings at the host system of questionable value since the network communication processing costs rise as the segment size increases due to retransmission of entire segments when a single fragment is lost or is in error.
An improved MTU determination scheme is outlined in U.S. Pat. No. 5,751,970. This patent outlines a process for determining and selecting an optimum segment size for transferring data across a network. In this method, the cost of transferring a segment equal in size to the MTU is sequentially compared to the cost of transferring segments which are integer incremented multiples of the MTU. When the comparison indicates that the cost of the incremented segments exceeds the cost of transferring the segment equal in size to the MTU, the sequential comparison is halted, and the segment size derived in the previous calculation is used for transferring the data. To do this calculation, an iterative procedure may be used or an approximate value can be calculated if certain characteristics of the network are known. Though using this non-iterative solution addresses the problem of increased handshake time that exists with both channel interrogation and an iterative approach, it does not accommodate changing network conditions. The changes in network conditions undermine the calculation of the MTU multiplier, causing the system to yield a sub-optimal segmentation size.
One problem not addressed by methods common in the art is that the system parameters vary in real time in a non-deterministic manner. Prior art treats network communications as either static or varying with time in a deterministic fashion. Network unpredictability is the result of stochastic processes that cannot be properly modelled. These unpredictable effects must be compensated for to achieve TDM Quality of Service (QoS) in a packet-based network.
As a result of industry""s desire to achieve TDM quality voice transmission the focus of attention has shifted from Internet telephony (carrying voice calls over the Internet) to IP telephony or Voice-over-IP (VoIP) using other IP networks, especially private network backbones. In its broadest sense, this is a move to packet based telephony, commonly called Voice over Packet (VoP), on private networks which has been prompted, in large part, by the need to guarantee a minimum level of connectivity bandwidth, while reducing congestion problems. The second benefit of this private network approach is that it affords a greater ability to predict network conditions, and to identify points of probable congestion.
Additionally, with a private network, it is possible to prioritise packets derived from real-time sources such as voice transmissions (henceforth referred to as voice packets) over packets derived from computer based information sources (henceforth referred to as data packets) utilising a queuing scheme. The Internet generally is unreliable for high quality voice telephony because the TCP/IP protocols currently do not provide for reserving bandwidth to guarantee QoS. Thus, the quality of VoIP calls is adversely affected by unpredictable network congestion that can cause packet delays or losses. For these reasons environments such as the public Internet or another public packet network, which are marked by dramatic and uncontrollable fluctuations in load, cannot guarantee an acceptable voice connection. Private networks, using either IP or another packet oriented protocol, can provide high quality voice services because their traffic can be managed to a higher degree.
This ability to assign higher priority to a particular type of packet is termed Grade of Service (GoS) in the art. Though present implementations are an improvement over standard, unprioritised IP, they are not as effective as the TDM-world""s QoS guarantee, because GoS is only a relative guarantee. In effect GoS says that it will transmit one type of packet ahead of another, but is limited in both the number of grades available and in its ability to guarantee that a packet, of any grade, will be reliably received. In comparison QoS is an absolute and quantifiable guarantee, which is able to deliver higher priority packets over lower priority ones. This obstacle, along with several others, is overcome by the present invention.
It is an object of this invention to provide a solution to the above mentioned obstacles by providing a method of communicating Voice over IP (VoIP) gateways that provides voice Quality of Service (QoS) comparable to the Time Division Multiplexing (TDM) realm of traditional telephony. The method is primarily concerned with reducing packet jitter and delay at the launching gateway.
It is another object of this invention to have the jitter and delay introduced at the launching end compensated for at the receiving gateway by mechanisms such as a jitter buffer.
It is yet another object of the invention to have the launching gateway reduce impairments due to limitations in the jitter buffer size to negligible amounts. The reduction of jitter provided for herein aids in allowing TDM-Quality service using packet based transmission networks.
It is yet another object of this invention to provide a method of interleaving other types of real-time data, such as facsimile or video, with non-real-time data over a stream of mixed data units, such as packets, that combine both types of data while giving a higher priority to the real-time data.
The interleaving method disclosed herein consists of a number of discrete concepts and mechanisms that when used together in the following manner provides consistent high-quality transmission of real-time data over IP or other packet/frame/cell-based networks. The elements required for this method include:
1. Time-slot co-ordination
2. Dynamic MTU algorithm
3. Multiple queue egress traffic management system (e.g., high/low priority queues or real-time/non-real-time queues) that is synchronised with the co-ordination of time slots.
Time-slot co-ordination is a concept that is novel in packet based networks, though it is well used in the TDM environment.
TDM-Quality Voice over Packet is particularly intended for those situations where QoS must be provided to support real-time applications such as voice or video.
It is an object of the present invention to provide a communication system for interleaving non-real-time data (NRD) and real-time data (RTD), said RTD representing at least one of n analogue signals, each signal received from at least one of n calls, for transmission over a data network, having a predetermined network bandwidth, said system comprising four elements. The first element is a non-real-time queue for receiving the NRD. The second element is a real-time queue for receiving the RTD. The third element is a network interface responsive to the non-real-time queue and the real-time queue for combining a maximum transmission unit (MTU) that contains a segment of the NRD, with a real-time window (RTW) that contains a segment of the RTD, into a launch window having a predetermined launch interval. The fourth element is an MTU calculation unit for determining a permissible size in bits for the MTU equal to at most the launch window size minus a size for the RTW suitable to permit a synchronised transmission of said RTD within the launch interval based on the network bandwidth. One aspect of the current invention is to provide a communication system, as described above further comprising fragmentation means responsive to the MTU calculation unit for fragmenting the NRD into a plurality of data fragments, each fragment having a size suitable for fitting within one of a corresponding plurality of MTUs. Another aspect of the current object of the invention is to provide a communication system as described above, wherein the launch window has a size in bits equal to the product of the launch interval in seconds and the network bandwidth in bits per second. A further aspect of the current invention is a communication system as described above, wherein the RTW has a size in bits equal to a predetermined number of protocol overhead bits plus a product of n, a pre-selected call density coefficient and a pre-selected block size in bits. Yet another aspect of the current invention is a communication system as described above, wherein each one of the n calls has a respective call density coefficient (CDC) and a respective block size, and wherein the RTW has a size in bits equal to a predetermined number of protocol overhead bits plus a sum of n products corresponding to the n call, each product obtained by multiplying the respective CDC and the respective block size in bits of each one of the n calls. Another aspect of the current invention is a communication system as described above, wherein the at least one of the n calls carries a voice signal. Another aspect of the current invention is a communication system as described above, wherein the at least one of the n calls carries a facsimile signal. Another aspect of the current invention is a communication system as described above, wherein the at least one of the n calls carries a video signal.
Another object of the current invention is a method of interleaving non-real-time data (NRD) with real-time data (RTD) representing analog signals from at least one of n calls, into a combined data stream, to be transmitted over a data network having a predetermined bandwidth, said method comprising the following three steps. The first step is the receiving and queuing the NRD. The second step is the receiving and queuing the RTD. The third step is the filling of a segment of the RTD into a real-time window (RTW) to form a first part of a launch window having a pre-selected size and a predetermined launch interval, wherein the RTW has a size suitable to permit a synchronised transmission of the RTD within the launch interval based on the network bandwidth. The fourth step is the filling of a segment of the NRD into a maximum transmission unit (MTU) to form a second part of the launch window, wherein the MTU has a size equal to at most the launch window size minus the RTW size. One aspect of this object of the invention is an interleaving method as described above, further comprising the step of fragmenting the NRD into a plurality of data fragments, each fragment having a size suitable for fitting within one of a corresponding plurality of MTUs. Another aspect of the current invention is an interleaving method as described above, wherein the launch window has a size in bits equal to the product of the launch interval in seconds and the network bandwidth in bits per second. Yet another aspect of the current invention is an interleaving method as described above, wherein the RTW has a size in bits equal to a predetermined number of protocol overhead bits plus a product of n, a pre-selected call density coefficient and a pre-selected block size in bits. Yet a further aspect of the current invention is an interleaving method as described above, wherein each one of the n calls has a respective call density coefficient (CDC) and a respective block size, and wherein the RTW has a size in bits equal to a predetermined number of protocol overhead bits plus a sum of n products corresponding to the n call, each product obtained by multiplying the respective CDC and the respective block size in bits of each one of the n calls. Another aspect of the current invention is an interleaving method as described above, wherein the at least one of the n calls carries a voice signal. Another aspect of the current invention is an interleaving method as described above, wherein the at least one of the n calls carries a facsimile signal. Another aspect of the-current invention is an interleaving method as described above, wherein the at least one of the n calls carries a video signal.